class Solution {
public:
    int search(vector<int>& nums, int target) {
        int sz=nums.size();
        int left=0,right=sz-1,mid=0;
        while(left<=right)
        {
            mid=left+(right-left)/2;
            if(nums[mid]==target) return mid;
            if(nums[left]<=nums[mid])
            {
                if(nums[left]<=target&&target<nums[mid])
                    right=mid-1;
                else 
                    left=mid+1;
            }
            else
            {
                if(nums[mid]<target&&target<=nums[right])
                    left=mid+1;
                else
                    right=mid-1;
            } 
        }
        return -1;
    }
};
//分成两个阶段，判断target是否在阶段里面
